// 1、无头单向非循环链表实现
public class SingleLinkedList {
    public static class ListNode{
        private int data;
        private ListNode next;

        public ListNode(int data) {
            this.data = data;
        }

    }
    private ListNode head;
    private int size;

    public SingleLinkedList(ListNode head, int size) {
        this.head = head;
        this.size = 0;
    }

    //头插法
    public void addFirst(int data){
        ListNode newNode=new ListNode(data);
        if(head==null){
            head=newNode;
            return;
        }
        newNode.next=head;
        head=newNode;
        size++;
    }
    //尾插法
    public void addLast(int data){
        ListNode newNode=new ListNode(data);
        if (head==null){
            head=newNode;
        }
        ListNode cur=head;
        while (cur.next!=null){
            cur=cur.next;
        }
        cur.next=newNode;
        size++;
    }

    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data){
        if(index<0||index>size){
            throw new IndexOutOfBoundsException("索引超出范围");
        }
        ListNode newNode=new ListNode(data);
        //索引在头结点
        if(index==0){
            addFirst(data);
            return true;
        }
        //索引在尾结点
        if(index==size-1){
            addLast(data);
            return true;
        }
        //找到索引为index的前一个结点cur
        ListNode cur=head;
        int count=0;
        while(count!=index-1){
            cur=cur.next;
            count++;
        }

        //插入新结点
        newNode.next=cur.next;
        cur.next=newNode;
        size++;
        return true;
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur=head;
        //直接从表头开始,一个个找
        while (cur!=null){
            if(cur.data==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        //表头为key删除后返回
        if(head.data==key){
            head=head.next;
            size--;
            return;
        }
        //key不在表头
        ListNode cur=head;
        while (cur != null &&cur.next!=null){
            if(cur.next.data==key){
                cur.next=cur.next.next;
                size--;
                break;
            }else{
                cur=cur.next;
            }
        }

    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
//        ListNode cur=head; //错误:得先处理了表头为key的情况才能给cur赋值为head
        //处理表头可能为key的情况
        //但是这种方法有可能会出现空指针异常
        //当链表元素都是key的时候，最后一个元素删除后，head为null了，此时又返回执行head.data==key,head.data这里就会报错
//        while(head.data==key){
//            head=head.next;
//            size--;
//        }
        ListNode cur=head;
        //处理除了表头外为key的情况
        while(cur != null &&cur.next!=null){
            if(cur.next.data==key){
                cur.next=cur.next.next;
                size--;
            }else {
                cur = cur.next;
            }
        }
        if(head.data==key){
            head=head.next;
            size--;
        }
    }
    //得到单链表的长度
    public int size(){
        return size;
    }
    public void display(){
        ListNode cur=head;
        while (cur!=null){
            System.out.print(cur.data+"->");
            cur=cur.next;
        }
        System.out.print("null");
    }
    public void clear(){
        head=null;
        size=0;
    }
}